package com.lcz.suanfa;

import org.junit.Test;

import java.time.temporal.ValueRange;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Locale;
import java.util.Map;

/**
 * <pre>
 * <img width="128" height="110" src="https://tse3-mm.cn.bing.net/th/id/OIP-C.en-w_oH-yn2UsSRfWnOsGAHaGY?w=198&h=180&c=7&r=0&o=5&dpr=1.25&pid=1.7" alt="马刺">
 * 作者:     <a href="https://github.com/liuchuanzheng">刘传政</a>
 * 创建时间:  9:46 2022/2/16 0016
 * QQ:      1052374416
 * 电话:     18501231486
 * 描述:
 * </pre>
 */
public class Suanfa_字符串 {
    @Test
    public void test_反转字符串() {

    }

    public void reverseString(char[] s) {
        int shang = s.length / 2;
        char temp;
        for (int i = 0; i <= shang - 1; i++) {
            temp = s[i];
            s[i] = s[s.length - 1 - i];
            s[s.length - 1 - i] = temp;
        }

    }

    //整数反转
    public int reverse(int x) {
        String s = x + "";
        StringBuilder sb = new StringBuilder();
        if (s.startsWith("-")) {
            sb.append("-");
        }

        for (int length = s.toCharArray().length - 1; length >= 0; length--) {
            char c = s.charAt(length);
            if (c != '-') {
                sb.append(c);
            }
        }
        try {
            int i = Integer.parseInt(sb.toString());
            return i;
        } catch (Exception e) {
            return 0;
        }

    }

    @Test
    public void test_字符串中的第一个唯一字符() {
        int index = firstUniqChar("aabb");
        System.out.println(index);
    }

    //字符串中的第一个唯一字符
    public int firstUniqChar(String s) {
        LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                int value = map.get(c) + 1;
                map.put(c, value);
            } else {
                map.put(c, 1);
            }
        }
        Iterator<Map.Entry<Character, Integer>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Character, Integer> next = iterator.next();
            if (next.getValue() == 1) {
                return s.indexOf(next.getKey());
            }

        }

        return -1;
    }

    //有效的字母异位词
    public boolean isAnagram(String s, String t) {
        if (t.length() != s.length()) {
            return false;
        }
        HashMap<Character, Integer> mapS = new HashMap<>();
        HashMap<Character, Integer> mapT = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (mapS.containsKey(c)) {
                int value = mapS.get(c) + 1;
                mapS.put(c, value);
            } else {
                mapS.put(c, 1);
            }

            char st = t.charAt(i);
            if (mapT.containsKey(st)) {
                int value = mapT.get(st) + 1;
                mapT.put(st, value);
            } else {
                mapT.put(st, 1);
            }

        }

        if (mapS.size() != mapT.size()) {
            return false;
        }
        Iterator<Map.Entry<Character, Integer>> iterator = mapS.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Character, Integer> next = iterator.next();
            if (!next.getValue().equals(mapT.get(next.getKey()))) {
                return false;
            }
        }
        return true;
    }

    @Test
    public void test_验证回文串() {
        String s = "race a car";
        System.out.println(isPalindrome(s));
    }

    //验证回文串
    public boolean isPalindrome(String s) {
        if (s.isEmpty()) {
            return true;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (Character.isLetterOrDigit(c)) {
                sb.append(c);
            }
        }
        StringBuilder sbr = new StringBuilder();
        for (int j = sb.length() - 1; j >= 0; j--) {
            char c = sb.charAt(j);
            sbr.append(c);
        }
        return sb.toString().equalsIgnoreCase(sbr.toString());
    }

    @Test
    public void test_字符串转换整数() {
        String s = "words and 987";
        System.out.println(myAtoi(s));
    }

    //状态机解决
    public int myAtoi(String str) {
        Automaton automaton = new Automaton();
        int length = str.length();
        for (int i = 0; i < length; ++i) {
            automaton.get(str.charAt(i));
        }
        return (int) (automaton.sign * automaton.ans);
    }

    class Automaton {
        public int sign = 1;
        public long ans = 0;
        private String state = "start";
        private Map<String, String[]> table = new HashMap<String, String[]>() {{
            put("start", new String[]{"start", "signed", "in_number", "end"});
            put("signed", new String[]{"end", "end", "in_number", "end"});
            put("in_number", new String[]{"end", "end", "in_number", "end"});
            put("end", new String[]{"end", "end", "end", "end"});
        }};

        public void get(char c) {
            state = table.get(state)[get_col(c)];
            if ("in_number".equals(state)) {
                ans = ans * 10 + c - '0';
                ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
            } else if ("signed".equals(state)) {
                sign = c == '+' ? 1 : -1;
            }
        }

        private int get_col(char c) {
            if (c == ' ') {
                return 0;
            }
            if (c == '+' || c == '-') {
                return 1;
            }
            if (Character.isDigit(c)) {
                return 2;
            }
            return 3;
        }
    }

    //实现 strStr() 函数。
    //
    //给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1
    //
    //作者：力扣 (LeetCode)
    //链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnr003/
    //来源：力扣（LeetCode）
    //著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    public int strStr(String haystack, String needle) {
        int i = haystack.indexOf(needle);
        return i;
    }

    //暴力匹配
    public int strStr2(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        for (int i = 0; i + m <= n; i++) {
            boolean flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;

    }

    //外观数列
    public String countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        StringBuilder sb = new StringBuilder();
        String last = countAndSay(n - 1);
        char current = 'a';
        int currentCount = 0;
        for (int i = 0; i < last.length(); i++) {
            char c = last.charAt(i);
            if (current == c) {
                currentCount++;
            } else {
                if (current != 'a') {
                    sb.append(currentCount + "");
                    sb.append(current + "");
                }
                current = c;
                currentCount = 1;
            }
        }
        if (current != 'a') {
            sb.append(currentCount + "");
            sb.append(current + "");
        }
        return sb.toString();
    }

    //最长公共前缀
    public String longestCommonPrefix(String[] strs) {
        if (strs[0].length() == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String common = "";
        for (int i = 0; i < strs[0].length(); i++) {
            common = common + strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                String str = strs[j];
                if (str.startsWith(common)) {
                    if (j == strs.length - 1 && i == strs[0].length() - 1) {
                        //最后一个
                        return common;
                    }
                } else {
                    return common.substring(0,common.length()-1);
                }
            }
        }
        return "";
    }
}
